package problem90_SubSet2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class MySolution {
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> result=new LinkedList<>();
		dfs(new LinkedList<>(), result, 0, nums);
		return result;
    }
	
	private void dfs(List<Integer> tmp,List<List<Integer>> result,int start,int nums[]){
		result.add(new ArrayList<Integer>(tmp));
		for(int i=start;i<nums.length;i++){
			if(existsBefore(nums,start,i))	continue;
			tmp.add(nums[i]);
			dfs(tmp,result,i+1,nums);
			tmp.remove(tmp.size()-1);
		}
	}
	
	private boolean existsBefore(int nums[],int start,int i ){
		for(int j=start;j<i;j++){
			if(nums[i]==nums[j])
				return true;
		}
		return false;
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().subsetsWithDup(new int[]{1,2,2}));
	}
}
